/**
 * @param {number} n
 * @return {string[]}
 */
/* 
为了生成所有有效的括号组合，可以使用回溯法。
通过递归地添加左括号和右括号，并确保每次添加后的组合仍然有效，最终生成所有符合条件的组合。

方法思路
递归回溯：维护当前字符串、左括号数量和右括号数量，递归添加括号。
添加条件：
可以添加左括号的条件：左括号数量小于 n。
可以添加右括号的条件：右括号数量小于左括号数量。
终止条件：当左括号和右括号数量都等于 n 时，记录当前字符串。
*/
var generateParenthesis = function (n) {
  const result = [];

  // 回溯函数：path表示当前括号组合，left表示左括号数量，right表示右括号数量
  const backtrack = (path, left, right) => {
    // 当左右括号数量都等于n时，加入结果集
    if (left === n && right === n) {
      result.push(path);
      return;
    }

    // 可以添加左括号的条件：左括号数量小于n
    if (left < n) {
      backtrack(path + '(', left + 1, right);
    }

    // 可以添加右括号的条件：右括号数量小于左括号数量
    if (right < left) {
      backtrack(path + ')', left, right + 1);
    }
  };

  // 从空字符串开始回溯
  backtrack('', 0, 0);

  return result;
};